package com.chen.demo.javase.algorithm.leetcode.editor.cn;
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 
// 👍 4347 👎 0

import java.util.Arrays;

public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        int[] nums = {1, 2};
        int[] nums2 = {3, 4};
        // System.out.println(solution.findMedianSortedArrays(nums, nums2));
        nums = new int[]{1,3};
        nums2 = new int[]{2};
        System.out.println(solution.findMedianSortedArrays(nums, nums2));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] sortResult;
            if (nums1.length == 0) {
                sortResult = nums2;
            } else if (nums2.length == 0) {
                sortResult = nums1;
            } else {
                // 合并两个有序数组
                sortResult = mergeSortedArray(nums1, nums2);
            }
            if (sortResult.length == 1) {
                return sortResult[0];
            }
            return sortResult.length % 2 != 0 ? sortResult[sortResult.length / 2] :
                    (sortResult[sortResult.length / 2] + sortResult[sortResult.length / 2 - 1]) / 2.0;
        }

        /**
         * 合并两个有序数组
         *
         * @param nums1 num1
         * @param nums2 num2
         * @return 有序数组
         */
        private int[] mergeSortedArray(int[] nums1, int[] nums2) {
            // 依次填充数组最后一个元素
            int firstIndex = 0;
            int secondIndex = 0;
            int[] result = new int[nums1.length + nums2.length];
            int index = 0;
            while (firstIndex <= nums1.length - 1 && secondIndex <= nums2.length - 1) {
                if (nums1[firstIndex] > nums2[secondIndex]) {
                    result[index++] = nums2[secondIndex++];
                } else {
                    result[index++] = nums1[firstIndex++];
                }
                //
                if (firstIndex >= nums1.length) {
                    while (secondIndex <= nums2.length - 1) {
                        result[index++] = nums2[secondIndex++];
                    }
                }
                if (secondIndex >= nums2.length) {
                    while (firstIndex <= nums1.length -1) {
                        result[index++] = nums1[firstIndex++];
                    }
                }
            }
            return result;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}